Nothing-up-my-sleeve Number
   HOME

TheInfoList



OR:

In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
, nothing-up-my-sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and
cipher In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is ''encipherment''. To encipher or encode i ...
s. These algorithms often need randomized constants for mixing or initialization purposes. The cryptographer may wish to pick these values in a way that demonstrates the constants were not selected for a nefarious purpose, for example, to create a backdoor to the algorithm. These fears can be allayed by using numbers created in a way that leaves little room for adjustment. An example would be the use of initial digits from the number as the constants. Using digits of millions of places after the decimal point would not be considered trustworthy because the algorithm designer might have selected that starting point because it created a secret weakness the designer could later exploit. Digits in the positional representations of real numbers such as , ''e'', and irrational roots are believed to appear with equal frequency (see
normal number In mathematics, a real number is said to be simply normal in an integer base b if its infinite sequence of digits is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b. A number is said to ...
). Such numbers can be viewed as the opposite extreme of Chaitin–Kolmogorov random numbers in that they appear random but have very low
information entropy In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random variable X, which takes values in the alphabet \ ...
. Their use is motivated by early controversy over the U.S. Government's 1975
Data Encryption Standard The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cr ...
, which came under criticism because no explanation was supplied for the constants used in its S-box (though they were later found to have been carefully selected to protect against the then-classified technique of differential cryptanalysis).
Bruce Schneier Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is a Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman Klein Ce ...
. ''Applied Cryptography'', second edition, John Wiley and Sons, 1996, p. 278.
Thus a need was felt for a more transparent way to generate constants used in cryptography. "Nothing up my sleeve" is a phrase associated with magicians, who sometimes preface a magic trick by holding open their sleeves to show they have no objects hidden inside.


Examples

*
Ron Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Int ...
used the trigonometric
sine In mathematics, sine and cosine are trigonometric functions of an angle. The sine and cosine of an acute angle are defined in the context of a right triangle: for the specified angle, its sine is the ratio of the length of the side that is opp ...
function to generate constants for the widely used MD5 hash. * The U.S.
National Security Agency The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collectio ...
used the
square root In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or  ⋅ ) is . For example, 4 and −4 are square roots of 16, because . ...
s of small integers to produce the constants used in its "Secure Hash Algorithm"
SHA-1 In cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20- byte) hash value known as a message digest – typically rendered as 40 hexadec ...
. The
SHA-2 SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compressi ...
functions use the square roots and cube roots of small primes. SHA-1 also uses 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 as its initial hash value. * The Blowfish encryption algorithm uses the binary representation of (without the initial 3) to initialize its
key schedule In cryptography, the so-called product ciphers are a certain kind of cipher, where the (de-)ciphering of data is typically done as an iteration of ''rounds''. The setup for each round is generally the same, except for round-specific fixed val ...
.Blowfish Paper
/ref> * RFC 3526 describes prime numbers for
internet key exchange In computing, Internet Key Exchange (IKE, sometimes IKEv1 or IKEv2, depending on version) is the protocol used to set up a security association (SA) in the IPsec protocol suite. IKE builds upon the Oakley protocol and ISAKMP.The Internet Key Exc ...
that are also generated from . * The S-box of the
NewDES In cryptography, NewDES is a symmetric key block cipher. It was created in 1984–1985 by Robert Scott as a potential DES replacement. Despite its name, it is not derived from DES and has quite a different structure. Its intended niche as a DES r ...
cipher is derived from the
United States Declaration of Independence The United States Declaration of Independence, formally The unanimous Declaration of the thirteen States of America, is the pronouncement and founding document adopted by the Second Continental Congress meeting at Pennsylvania State House ...
. * The AES candidate DFC derives all of its arbitrary constants, including all entries of the S-box, from the binary expansion of . * The
ARIA In music, an aria ( Italian: ; plural: ''arie'' , or ''arias'' in common usage, diminutive form arietta , plural ariette, or in English simply air) is a self-contained piece for one voice, with or without instrumental or orchestral accompa ...
key schedule uses the binary expansion of 1/. * The key schedule of the
RC5 In cryptography, RC5 is a symmetric-key block cipher notable for its simplicity. Designed by Ronald Rivest in 1994, ''RC'' stands for "Rivest Cipher", or alternatively, "Ron's Code" (compare RC2 and RC4). The Advanced Encryption Standard (AES) c ...
cipher uses binary digits from both and the
golden ratio In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0, where the Greek letter phi ( ...
. * Multiple ciphers including TEA and Red Pike use 2654435769 or 0x9e3779b9 which is , where ''ϕ'' is the golden ratio. * The BLAKE hash function, a finalist in the
SHA-3 SHA-3 (Secure Hash Algorithm 3) is the latest member of the Secure Hash Algorithm family of standards, released by NIST on August 5, 2015. Although part of the same series of standards, SHA-3 is internally different from the MD5-like stru ...
competition, uses a table of 16 constant words which are the leading 512 or 1024 bits of the
fractional part The fractional part or decimal part of a non‐negative real number x is the excess beyond that number's integer part. If the latter is defined as the largest integer not greater than , called floor of or \lfloor x\rfloor, its fractional part ca ...
of . * The key schedule of the KASUMI cipher uses 0x123456789ABCDEFFEDCBA9876543210 to derive the modified key. * The
Salsa20 Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. Ch ...
family of ciphers use the ASCII string "expand 32-byte k" as constants in its block initialization process. *
Bcrypt bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive ...
uses the string "OrpheanBeholderScryDoubt" as an initialization string


Counterexamples

*The Streebog hash function S-box was claimed to be generated randomly, but was reverse-engineered and proven to be generated algorithmically with some "puzzling" weaknesses. *The
Data Encryption Standard The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cr ...
(DES) has constants that were given out by NSA. They turned out to be far from random, but instead made the algorithm resilient against differential cryptanalysis, a method not publicly known at the time. * Dual_EC_DRBG, a
NIST The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sc ...
-recommended cryptographic
pseudo-random bit generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
, came under criticism in 2007 because constants recommended for use in the algorithm could have been selected in a way that would permit their author to predict future outputs given a sample of past generated values. In September 2013 ''The New York Times'' wrote that "internal memos leaked by a former NSA contractor,
Edward Snowden Edward Joseph Snowden (born June 21, 1983) is an American and naturalized Russian former computer intelligence consultant who leaked highly classified information from the National Security Agency (NSA) in 2013, when he was an employee and s ...
, suggest that the NSA generated one of the random number generators used in a 2006 NIST standard—called the Dual EC DRBG standard—which contains a back door for the NSA." * P curves are standardized by NIST for
elliptic curve cryptography Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide e ...
. The coefficients in these curves are generated by hashing unexplained random seeds, such as: ** P-224: bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5. ** P-256: c49d3608 86e70493 6a6678e1 139d26b7 819f7e90. ** P-384: a335926a a319a27a 1d00896a 6773a482 7acdac73. Although not directly related, after the backdoor in Dual_EC_DRBG had been exposed, suspicious aspects of the NIST's P curve constants led to concerns that the NSA had chosen values that gave them an advantage in finding private keys. Since then, many protocols and programs started to use
Curve25519 In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security (256-bit key size) and designed for use with the elliptic curve Diffie–Hellman (ECDH) key agreement scheme. It is one ...
as an alternative to NIST P-256 curve.


Limitations

Bernstein and coauthors demonstrate that use of nothing-up-my-sleeve numbers as the starting point in a complex procedure for generating cryptographic objects, such as elliptic curves, may not be sufficient to prevent insertion of back doors. If there are enough adjustable elements in the object selection procedure, the universe of possible design choices and of apparently simple constants can be large enough so that a search of the possibilities allows construction of an object with desired backdoor properties.How to manipulate curve standards: a white paper for the black hat
Daniel J. Bernstein, Tung Chou, Chitchanok Chuengsatiansup, Andreas Hu ̈lsing, Eran Lambooij, Tanja Lange, Ruben Niederhagen, and Christine van Vredendaal, September 27, 2015, accessed June 4, 2016


Footnotes

{{reflist


References

*
Bruce Schneier Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is a Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman Klein Ce ...
. ''Applied Cryptography'', second edition. John Wiley and Sons, 1996. * Eli Biham,
Adi Shamir Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identifica ...
, (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology — CRYPTO '90. Springer-Verlag. 2–21. Random number generation Cryptography Transparency (behavior)